Toán học rời rạc: Cơ sở của logic tuần tự

Sự chuyển đổi từ logic tổ hợp sang logic tuần tự mang đến yếu tố thời gian, nơi đầu ra của mạch không còn chỉ phụ thuộc vào các đầu vào hiện tại mà còn phụ thuộc vào lịch sử hệ thống. Sự "nhớ" này được xác lập về mặt vật lý và toán học trong thành phần Trễ thời gian đơn vị, đóng vai trò là khối xây dựng cơ bản cho mọi mô hình tính toán dựa trên trạng thái.

Mạch tổ hợp so với mạch tuần tự

Trong thế giới số, chúng ta phân biệt giữa các hệ thống sống trong "hiện tại" và các hệ thống nhớ về "quá khứ":

Mạch tổ hợp: Chúng không có bộ nhớ. Giống như một công tắc đèn đơn giản chỉ ở hai trạng thái bật hoặc tắt, đầu ra hoàn toàn phụ thuộc vào các giá trị đầu vào hiện tại.
Mạch tuần tự: Chúng sử dụng vòng hồi tiếp để tích hợp các đầu vào quá khứ vào quá trình ra quyết định hiện tại. Chúng thực sự nối liền khoảng cách giữa các cổng logic đơn giản và các máy trạng thái hữu hạn phức tạp.

Định nghĩa 12.1.1

Một trễ thời gian đơn vị là một thành phần cơ bản chấp nhận một bit $x_t$ làm đầu vào tại thời điểm $t$ và trả ra $x_{t-1}$, bit đã được đưa vào tại thời điểm $t-1$.

Khái niệm trạng thái

Việc tích hợp các trễ thời gian đơn vị cho phép tạo ra trạng thái. Cách sắp xếp các bit đã lưu giữ sẽ xác định cách máy phản ứng với các chuỗi tín hiệu tương lai. Không có sự sắp thứ tự này, việc tính toán sẽ bị giới hạn ở các đánh giá tĩnh.

So sánh công tắc đảo chiều

Hãy xem xét một "công tắc đảo chiều" số, nơi một nút duy nhất bật và tắt đèn. Một mạch tổ hợp chỉ có thể phát hiện xem nút đó có đang hiện tại được nhấn. Tuy nhiên, bằng cách sử dụng một trễ thời gian đơn vị để lưu trữ trạng thái trước đó của đèn ($x_{t-1}$), một mạch tuần tự có thể xác định rằng nếu nút được nhấn và đèn trước đó đã tắt ($x_{t-1}=0$), thì đầu ra mới nên là bật ($x_t=1$).

🎯 Nguyên lý cốt lõi

Bộ nhớ trong khoa học máy tính được biểu diễn toán học bằng các trễ. Một mạch tuần tự thực chất là logic tổ hợp bao quanh bởi một vòng hồi tiếp chứa các trễ thời gian đơn vị.

CÂU HỎI 1

Thành phần nào là bắt buộc để biến đổi một mạch tổ hợp thành mạch tuần tự?

Một cổng AND

Một trễ thời gian đơn vị

Một bộ đảo

Nguồn điện

CÂU HỎI 2

Nếu một trễ thời gian đơn vị nhận một dãy bit 1, 0, 1 tại các thời điểm t=1, 2, 3, đầu ra của nó tại thời điểm t=3 là bao nhiêu?

xₜ₊₁

NULL

CÂU HỎI 3

Đầu ra của một mạch tổ hợp phụ thuộc vào:

Chỉ các đầu vào hiện tại

Các đầu vào quá khứ và hiện tại

Các đầu vào tương lai

Chỉ đồng hồ nội bộ

CÂU HỎI 4

Trong biểu diễn toán học của một mạch, ký hiệu $z^{-1}$ đại diện cho điều gì?

Logic đảo ngược

Một trễ thời gian đơn vị

Trạng thái điện áp bằng không

Căn bậc hai của đầu vào

CÂU HỎI 5

Tại sao 'hồi tiếp' lại thiết yếu trong Máy trạng thái hữu hạn?

Để tăng điện áp của tín hiệu

Để cho phép trạng thái hiện tại của máy ảnh hưởng đến trạng thái tiếp theo

Để ngăn mạch bị quá nhiệt

Để loại bỏ nhu cầu về các bit đầu vào

Ví dụ nghiên cứu: Chuỗi FSM và đặc trưng hóa

Phân tích Ví dụ 12.1.5 và các vấn đề mở rộng hơn

Ban đầu, hệ thống ở trạng thái $\sigma_0$. Chúng ta định nghĩa các máy thông qua hàm trạng thái tiếp theo và hàm đầu ra, thường được minh họa bằng sơ đồ chuyển trạng thái.

Câu hỏi 1

Tìm chuỗi đầu ra tương ứng với chuỗi đầu vào $aababba$ cho máy trạng thái hữu hạn trong Ví dụ 12.1.5.

Lời giải tham khảo: Đối với một FSM điển hình như Ví dụ 12.1.5 (giả sử đảo chiều tại 'a' và giữ nguyên tại 'b'), nếu $\sigma_0$ là trạng thái khởi đầu: 1. Nhập 'a' → Trạng thái $\sigma_1$, Đầu ra '1'. 2. Nhập 'a' → Trạng thái $\sigma_0$, Đầu ra '0'. 3. Nhập 'b' → Trạng thái $\sigma_0$, Đầu ra '0'. 4. Nhập 'a' → Trạng thái $\sigma_1$, Đầu ra '1'. 5. Nhập 'b' → Trạng thái $\sigma_1$, Đầu ra '1'. 6. Nhập 'b' → Trạng thái $\sigma_1$, Đầu ra '1'. 7. Nhập 'a' → Trạng thái $\sigma_0$, Đầu ra '0'.
Chuỗi đầu ra: 1001110.

Câu hỏi 2

Xác định một flip-flop theo nghĩa của các trễ.

Lời giải tham khảo: Một flip-flop là một mạch tuần tự sử dụng một vòng hồi tiếp và ít nhất một trễ thời gian đơn vị để lưu trữ một bit thông tin, duy trì trạng thái đầu ra ngay cả khi kích thích đầu vào ban đầu đã được loại bỏ.

Câu hỏi 3

Đặc trưng hóa các chuỗi được chấp nhận bởi các bộ tự động trạng thái hữu hạn trong các bài tập 1-9.

Lời giải tham khảo: Các bộ tự động trong các bài tập này thường xác định các ngôn ngữ chính quy. Đặc trưng bao gồm: 1. Các chuỗi chứa các đoạn con cụ thể (ví dụ: '001'). 2. Các chuỗi biểu diễn các số nhị phân chia hết cho hằng số $n$. 3. Các chuỗi có bội số cụ thể của số 0 hoặc số 1 (ví dụ: số lượng số 1 là chẵn). 4. Các chuỗi bắt đầu và kết thúc bằng cùng một ký tự. Các tập hợp này được gọi là Tập hợp chính quy.